package 剑指offer_leetcode;

import java.util.ArrayDeque;
import java.util.ArrayList;

public class 剑指Offer59_I_滑动窗口的最大值 {
    public int[] maxSlidingWindow(int[] nums, int k) {
        ArrayList<Integer> res = new ArrayList<>();
        if(nums.length>=k && k>0){
            ArrayDeque<Integer> dq = new ArrayDeque<>();
            for(int i=0;i<k;i++){
                while(!dq.isEmpty() && nums[dq.peekLast()]<nums[i])
                    dq.pollLast();
                dq.offerLast(i);
            }
            for(int i=k;i<nums.length;i++){
                res.add(nums[dq.peekFirst()]);
                while(!dq.isEmpty() && dq.peekFirst()<(i-k+1))
                    dq.pollFirst();
                while(!dq.isEmpty() && nums[dq.peekLast()]<nums[i])
                    dq.pollLast();
                dq.offerLast(i);
            }
            res.add(nums[dq.peekFirst()]);
        }
        if(res.isEmpty())
            return new int[0];
        int[] arr = new int[res.size()];
        for(int i=0;i<res.size();i++)
            arr[i] = res.get(i);
        return arr;
    }
}
